package main.Q1501_1600;

import java.util.*;

public class Q1551_1560 {
    public static void main(String[] args) {
        System.out.println("Question1551：");
        System.out.println("Question1552：两球之间的磁力");
        System.out.println("Question1553：");
        System.out.println("Question1554：");
        System.out.println("Question1555：");
        System.out.println("Question1556：");
        System.out.println("Question1557：可以到达所有点的最少点数目");
        System.out.println("Question1558：");
        System.out.println("Question1559：");
        System.out.println("Question1560：");
    }
}

class Question1552{
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length;
        int l = 1, r = (position[n-1]-position[0])/(m-1);
        while(l < r){
            int mid = l + (r-l)/2 +1;
            //position 能否可以使最小磁力为mid
            if(help(mid, position, m-1)){
                l = mid;
            }else r = mid-1;
        }
        return l;
    }

    public boolean help(int mid, int[] position, int m){
        int p = position[0];
        for(int i = 1; i < position.length; i++){
            if(position[i] - p < mid)continue;
            else {
                m--;
                if(m == 0)return true;
                p = position[i];
            }
        }
        return false;
    }
}

class Question1557{
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        Set<Integer> in=new HashSet<>(),out=new HashSet<>();//入度集合，出度集合
        for (List<Integer> edge:edges){
            Integer from=edge.get(0),to=edge.get(1);
            out.add(from);
            in.add(to);
            if (in.contains(to)) out.remove(to);
            if (in.contains(from)) out.remove(from);
        }
        return new ArrayList<>(out);
//        List<Integer> list=new ArrayList<>();//简便算法，效率不高
//        for (int i=0;i<n;i++) list.add(i);
//        for (List<Integer> edge:edges){
//            Integer end=edge.get(1);
//            if (list.contains(end)) list.remove(end);
//        }
//        return list;
    }
}